import java.util.ArrayList;
import java.util.List;

class Solution05 {
    // 定义数轴 右 > 下 > 左 > 上
    int[] dx = { 0, 1, 0, -1 };
    int[] dy = { 1, 0, -1, 0 };
    // 定义结果
    List<Integer> ret;
    // 行列
    int m, n;
    // 标记数组
    boolean[][] vis;

    public List<Integer> spiralOrder(int[][] matrix) {
        ret = new ArrayList<>();
        m = matrix.length;
        n = matrix[0].length;
        // 处理边界条件
        if (matrix == null || m == 0) {
            return ret;
        }
        vis = new boolean[m][n];
        int num = m * n;
        // 定义一个下标表示方向
        int index = 0;
        // 起始位置
        int x = 0, y = 0;
        for (int i = 0; i < num; i++) {
            // 添加结果
            ret.add(matrix[x][y]);
            // 进行标记
            vis[x][y] = true;

            // 计算下一个位置
            int ex = x + dx[index];
            int ey = y + dy[index];

            // 判断这个位置是否合法
            if (ex < 0 || ex >= m || ey < 0 || ey >= n || vis[ex][ey]) {
                // 不合法，改变方向
                index = (index + 1) % 4;
                ex = x + dx[index];
                ey = y + dy[index];
            }
            // 更换 x,y
            x = ex;
            y = ey;
        }
        return ret;
    }
}